模板(数据结构)

Posted on | Post modified: | In |
Words count in article: 1.9k

数组模拟单链表

  用数组模拟单链表，可以免去new占用的时间，加快算法执行速度。不过删除节点时会造成内存泄漏，但这一般是工程中考虑的问题，算法题跑时间就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// head 指向头节点， index 表示当前可用数组下标(只增)
int head = -1, v[N], next[N], index = 0;
//插入到头结点后（头插法），头节点是递增的
void add2head(int x){
    v[index] = x, ne[index] = head, head = index++;
}
//插入到下标k后
void add(int k, int x){
    v[index] = x, ne[index] = ne[k], ne[k] = index++;
}
//删除下标k后一个节点
void remove(int k){
    ne[k] = ne[ne[k]];
}

模拟栈和队列

栈只需要一个top指针，队列需要一个头指针一个尾指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//*********************//栈
int stk[N], top = 0;
//p指向栈顶，插入时先+p再赋值
stk[++top] = x;
//弹出
top--;
//判断空
if(top > 0) ;
//栈顶
stk[top];

//**********************//队列
//队尾插入，队首弹出
int q[N], head = 0, tail = -1;
//插入
q[++tail] = x;
//弹出
head ++;
// 判空
if(head <= tail);
// 取队头
q[head];

//*********************// 循环队列，hh和tt相等时为空，会损失一个容量
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)

单调栈

给定一个数列，输出每个数左边离它最近的比它小的数，不存在输出-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e5+10;

int n ;
int stk[N], tt=0;
int main(){
    cin.tie(0);
    cin >> n;

    for(int i = 0; i < n; i++)                          
    {
        int x;
        cin >> x;
        while( tt && stk[tt] >= x) tt--; //每次入栈前保证栈中之前的节点数值小于当前入栈值
        if(tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        
        stk[ ++tt ] = x;
    }
    return 0;
}

堆（以小根堆为例）

定义：完全二叉树，且父节点小于等于左右子节点。

特性：左节点下标（2x），右节点下标（2x+1）。

操作：down(x) : x变大了，那么需要往下调整。up(x) ：x变小了，需要往上调整。

1619358192132

建堆（O(n)做法）

从$n / 2$处，即倒数第2层开始，往跟节点遍历，对这些节点执行down操作。最后一层经历过上层的down操作一定是满足堆定义的。O(n) 证明如下：

倒数第二层有$ n / 4$个节点，则最多的操作的次数为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int heap[N], sz, m;

void down(int idx) { // 往下调整需要与两个子节点比较，因此比较两次
    int t = idx;
    if (2 * idx <= sz && heap[2 * idx] < heap[t]) t = 2 * idx;
    if (2 * idx + 1 <= sz && heap[2 * idx + 1] < heap[t]) t = 2 * idx + 1;
    if (idx != t) {
        swap(heap[t], heap[idx]);
        down(t);
    }
}

// 建堆，从后往前开始下调整即可
for (int i = sz / 2; i != 0; -- i) down(i);



void up(int idx) { // 往上调整只需要与父节点比较即可
    while (idx / 2 && heap[idx / 2] > heap[idx]) {
        swap(heap[idx / 2], heap[u]);
        idx /= 2;
    }
}


// 堆弹出的时候，将堆顶弹出，末尾放入堆顶，执行down操作。

并查集

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 并查集模板题，主要功能是合并两个集合、查找两个元素是否属于同一集合
// 主要想法是建立一个集合数字的哈希表，表中保存当前数字的祖宗节点，若祖宗节点相同，表示它们是一个集合。

#include <iostream>

using namespace std;

const int N = 1e5+10;

int p[N];

int find(int x) 
{
    if(p[x] != x) p[x] = find(p[x]);// 使用p[x]是为了合并集合时更改祖宗节点
    return p[x];
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) p[i] = i; // 1. 并查集需要初始化自己为根节点
    
    while(m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        
        if(op[0] == 'M') p[find(a)] = find(b);  // 2. 合并操作，将a的祖宗节点的祖宗节点设为b的祖宗节点
        else
        {
            if(find(a) == find(b)) printf("Yes\n");  // 查找操作
            else printf("No\n");
        }
    }
    
}

维护数量的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 1e5+10;
int p[N], num[N];
int n, m;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);   // 使用p[x]是为了合并集合时更改祖宗节点 ， 路径压缩
    return p[x];
}

int main(){
    cin >> n >> m;
    string op;
    int a, b;
    
    for(int i = 1; i <= n; i ++){
        p[i] = i;
        num[i] = 1;
    }
    
    while(m --){
        cin >> op;
        
        if(op == "C"){  // 合并操作
            cin >> a >> b;
            int x = find(a), y = find(b);
            if(x != y){
                p[x] = y;
                num[y] += num[x];  // b设为根节点
            }
        }
        else if(op == "Q1"){  // 查询是否在同一集合
            cin >> a >> b;
            find(a)==find(b) ? puts("Yes") : puts("No");
        }
        else{           // 查询数量
            cin >> a;
            printf("%d\n", num[find(a)]);
        }
    }
}

STL

  • priority_queue与set的区别

其中优先队列是由堆实现的，适用于每次只取前面的数的情况。而set是由BST实现的，可以快速查询某个数是否在set中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
ector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

set和map的公共操作：

	size()
    empty()
    clear()
    begin()/end()
    ++, -- 迭代器，返回前驱和后继，时间复杂度 O(logn)

set和map的区别：
    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反